#+TITLE: Интерпретатор SVGen
#+AUTHOR: Друан Филипп Сергеевич
#+LANGUAGE: ru

#+LATEX_CLASS:  article
#+LATEX_HEADER: \usepackage[T2A]{fontenc}
#+LATEX_HEADER: \usepackage[utf8]{inputenc}
#+LATEX_HEADER: \usepackage[russian]{babel}
#+LATEX_HEADER: \hypersetup{colorlinks=true}
#+LATEX_HEADER: \usepackage[margin=1in]{geometry}

* Пошаговое построение интерпретатора
Конечной целью создания нашего интерпретатора является реализация языка программирования SVGen.
Писать будем на Racket, так что сразу добавим заголовок для файла с кодом:
#+begin_src racket :tangle "lambda.rkt"
  #lang racket
  (require racket/block)
  (provide replace
           invoke
           exec)
#+end_src

И для тестов:
#+begin_src racket :tangle "tests.rkt"
  #lang racket
  (require rackunit ; Подключаем тестовый фреймворк
           "interpreter.rkt") ; Подключаем файл с нашим интерпретатором.
#+end_src

Для этого нам придётся пройти несколько этапов:

** Лисп, похожий на Лямбда-исчисление

*** Синтаксис и правила вычисления
На данном этапе у нас в языке имеется всего один тип данных - анонимная функция. Синтаксис этого языка мы можем определить вот так:
#+begin_src racket
  #|
  Expression = Symbol
             | Lambda-fuction
             | Fuction-call
             | Begin-form

  Symbol = Char {Char | Digit}

  Lambda-function = "(" "lambda" "(" {Symbol} ")" {Expression} ")"

  Function-call = "(" Expression {Expression} ")"

  Begin-form = "(" "begin" {Expressio} ")"

  Char = Тут всё понятно, любой печатный нечисловой символ, и не пробел.
  Digit = Любая цифра.
  |#
#+end_src
Как мы видим, в языке есть три вида выражений:
 - Символы, которыми обозначаются переменные
 - Лямбда функции
 - Вызовы лямбда функций
Чтож, давайте определим, как это всё будет вычисляться.
**** TODO Лямбда-функции
Лямбда-функции вычисляются сами в себя. То есть, если мы дадим нашему интерпретатору просто лямбда-функцию, он её и вернёт.

#+begin_src racket
  (lambda (a b c)
    (a b c))
  ; Вычисляется в саму себя, точно такую же функцию
  ; При этом вот такой вызов:
  ((lambda (a)
     (lambda (b c)
       (b (a c)))) ; Видете: a заменяетя на foo! -------------------+
   foo) ; Для краткости, пусть у функции в этом примере будет имя.  |
  ; Вернёт вот это:                                                 |
  (lambda (b c) ;                                                   |
    (b (foo c))) ; <------------------------------------------------+

#+end_src

Определим основные функции для работы с этими данными:
#+begin_src racket :tangle "lambda.rkt"
  (define (lambda-symbol? symbol)
    (equal? symbol
            'lambda))

  (define (lambda-fun? expr)
    (and (pair? expr)
         (lambda-symbol? (first expr))
         (list? (second expr))))

  ; [List of Symbol] [List of Expression] -> Lambda-fun
  (define (make-lf args body)
    (append (list 'lambda
                  args)
            body))

  (define (lf-formal-params lambda-fun)
    (second lambda-fun))

  (define (lf-body lambda-fun)
    (rest (rest lambda-fun)))
#+end_src

**** Символы
Символы являются переменными и только переменными. Если в теле функции встречается символ, которого нет среди параметров, это ошибка.

**** Вызов функции
Когда мы вызываем функцию, Сначала вычисляется первое выражение в списке вызова. После этого есть два варианта, как мы можем поступить: первый, сначала подставить все аргументы на место параметров, а потом уже вычислять, когда они будут вызываться. Это *нормальная модель вычислений*, именно она используется в Лямбда-исчислении.

Другой вариант - сначала вычислить аргументы, а потом подставить их значения на соответствующие места. Это называется *аппликативной моделью вычислений*. Пока мы используем подстановочную модель вычисления, они дают одинаковый результат, но когда нам нужно добавить побочные эффекты, всё становится гораздо сложнее. В SVGen мы должны рисовать (путём генерации XML), а значит у нас будут побочные эффекты. Так что нам понадобится аппликативный порядок вычисления.

В язык будет встроено *каррирование*. Если в вызове функции меньше фактических параметров, чем формальных, они будут подставлены на соответствующие места, но из функции вернётся другая функция, у которой будет те параметры, которые остались незаполненными. Вот пример:

#+begin_src racket
  ; Такой вызов:
  ((lambda (a b)
     (a b))
 
    (lambda (x) ; Эта Лямбда-функция - единственный фактический параметр.
      (x x)))

  ; Вернёт вот это:
  (lambda (b)
    (lambda (x)
      (x x))
    b)

#+end_src

Кроме этого, есть специальная форма begin. Она вычисляет все свои аргументы и возвращает значение последнего.

#+begin_src racket :tangle "lambda.rkt"
  (define (call-fun expr)
    (first expr))

  (define (call-args expr)
    (rest expr))

  (define (call? expr)
    (and (pair? expr)
         (not (lambda-fun? expr))
         (or (symbol?     (call-fun expr))
             (lambda-fun? (call-fun expr))
             (call?       (call-fun expr)))))
#+end_src



*** Ядро интерпретатора

**** replace

В основе Лямбда исчисления лежит подстановка. По этому, одна из главных функций в нашем интерпретаторе называется *replace*. Она принимает выражение и заменяет в нём все вхождения заданой переменной на то, что нам нужно.

Следовательно, сигнатура у неё такая: (replace expr from to) где expr - выражение, from - имя переменной, to - выражение, на которое мы будем её заменять.

Если выражение - это функция, у которой есть параметр с таким же именем, мы не будем ничего в ней заменять. Таким образом мы добьёмся того, что у нас будет лексическая область видимости. (АХТУНГ уточнить, верно ли здесь использовать такой термин).

Во всех остальных случаях, мы заменяем любые вхожндения переменной в выражение.

Это поведение иллюстрируется такими тестами:
#+begin_src racket :tangle "tests.rkt"
  (define (test-replace)
    (check-equal? (replace 'a
                           'a
                           'b)
                  'b)

    (check-equal? (replace '(lambda (a b)
                              (b a))
                           'a
                           '(lambda (x) x))
                  '(lambda (a b)
                     (b a))
                  "Формальные параметры имеют локальную область видимости, они экранируют переменные.")
    (check-equal? (replace '(lambda (a b)
                              ((lambda (x)
                                 (c x))
                               (b a)))
                           'c
                           '(lambda (x)
                              (x x)))
                  '(lambda (a b) ; Заметьте, что вот это:
                     ((lambda (x) ; Первый x,
                        ((lambda (x) ; А вот это - второй. Это разные переменные с одинаковыми именами.
                           (x x)) ; В этом выражении действует второй x.
                         x)) ; А в этом снова первый.
                      (b a))))

    (check-equal? (replace '(foo a b)
                           'foo
                           '(lambda (x y)
                              (x (y x))))
                  '((lambda (x y)
                      (x (y x)))
                    a
                    b))
    
    (check-equal? (replace '(foo a b) ; Если в выражении нет такой переменной, она не трогает его.
                           'baz
                           '(lambda (x) x))
                  '(foo a b)))

#+end_src

Давайте же напишем эту функцию!
#+begin_src racket :tangle "lambda.rkt"
  (define (contains? lst obj)
    (cond [(empty? lst)
           #f]
          [(equal? (first lst)
                   obj)
           #t]
          [else
           (contains? (rest lst)
                      obj)]))

  (define (replace expr from to)

    (define (replace-help expr) ; Определим вспомогательную функцию
      (replace expr from to))   ; Она должна принимать только одно выражение.
   ; Эта функция локальная, при каждом вызове replace она будет использовать
   ; Новые from и to, те, которые были передан в replace в этот раз.

    (cond [(symbol? expr)
           (if (equal? expr from) ; Если expr - это переменная, которую надо заменить
               to ; Мы её заменяем, вернув новое значение
               expr)] ; В противном случае, ничего с ней не делаем.

          [(lambda-fun? expr)
           (if (contains? (lf-formal-params expr)
                          from); По нашим правилам, если у функции есть такой-же параметр
               expr ; Мы ничего не торгаем.
               (make-lf (lf-formal-params expr) ; В противном случае
                        (map replace-help ; Заменяем все вхождения данной переменной
                             (lf-body expr))))]  ; В тело лямбда-фукции.

          [(call? expr) ; если наше выражение - это вызов функции
           (map replace-help ; мы просто заменяем переменную на её значение
                expr)] ; во всех выражениях, входящих в вызов.
          [else
           expr]))
#+end_src

**** invoke
Функция invoke [fn: Вообще, такая функция называется apply, но мы пишем на racket и такая функция у нас уже есть.] принимает функцию и список аргументов (фактических параметров), после чего подставляет эти аргументы на место соответствующих им формальных параметров.
Первый формальнй параметр заменяется на первый фактический и так далее, как и полагается в Лиспе.

Но! При этом, как уже было сказано выше, если фактических параметров меньше, чем формальных, мы вернём не результат функции, а её каррированную версию.

Кстати, вы помните, что в теле функции может быть несколько выражений? У нас, как и пологается в Лиспе, вернётся результат последнего выражения, хотя *вычисляет их все*.

Теперь тесты:

#+begin_src racket :tangle "tests.rkt"
  ; Смотрите, в нашем языке пока нет объявления функций, но это
  ; решается. Так как всё выражения в нашем Лямбда-исчислении
  ; записываются в виде вложенных списков Racket'а, мы эти
  ; списки кладём в переменные Racket'а
  (define equality-fun '(lambda (x)
                          x))
  (define self-fun     '(lambda (x)
                          (x x)))
  (define if-fun       '(lambda (test then else)
                          (test then else)))
  (define then-fun     '(lambda (then else)
                          then))
  (define else-fun     '(lambda (then else)
                          else))

#+end_src

#+begin_src racket :tangle "tests.rkt"
  (define (test-invoke)
    (check-equal? (invoke equality-fun
                          (list '(lambda (x y)
                                   x)))
                  '(lambda (x y)
                     x))
    (check-equal? (invoke if-fun
                          (list then-fun))
                  `(lambda (then else) ; В тестах используется quasiquote.
                     (,then-fun then else))) ; Иначе утонем во всех этих лямбдах.

    (check-equal? (invoke if-fun
                          (list then-fun
                                equality
                                self-fun))
                  equality)
    (check-equal? (invoke if-fun
                          (list else-fun
                                equality
                                self-fun))
                  self-fun)
    (check-exn exn:fail? ; Функция должна бросить ошибку
               (invoke equality-fun
                       (list else-fun ; Если параметров слишком много
                             equality
                             self-fun))))
#+end_src

Если фактических параметров больше, чем формальных -- *это ошибка!*

**** exec
ВАЖНО! exec - это ещё не execute.

Функция invoke, как ни странно, не самодостаточна. Она должна вычислять значения своего тела. А для этого нужна функция exec. Но, чтобы вычислить вызов функции, нам нужен invoke. Так они друг друга и вызывают.

Правила вычисления мы уже описали.

Осталось написать тесты!

#+begin_src racket :tangle "tests.rkt"
  (define (test-exec)
    (check-equal? (exec equality-fun)
                  equality-fun)

    (check-equal? (exec `(,equality-fun ,if-fun))
                  if-fun)

    (check-equal? (exec `(,if-fun
                              ,then-fun
                              ,equality-fun
                              ,self-fun))
                  equality-fun)

    (check-equal? (exec `(,if-fun
                              ,then-fun))
                  `(lambda (then else)
                     (,then-fun then else))))
#+end_src

**** Конечная реализация
Теперь у нас есть все тесты и мы можем реализовать функци invoke и evaluate.

#+begin_src racket :tangle "interpreter.rkt"
  (define (invoke fun args)
    (define formal-params (lf-formal-params fun))
    (define body          (lf-body          fun))

    (cond [(not (lambda-fun? fun))
           (error 'not-a-function "~A - это не функция." fun)]
          [(and (empty? args)
                (empty? formal-params))
           (exec (cons 'begin body))]

          [(and (not (empty? args))
                (empty? formal-params))
           (error 'more-arguments "Аргументов слишком много: ~A~%~%~A" fun args)]

          [(and (empty? args)
                (not (empty? formal-params)))
           fun]

          [(and (not (empty? args))
                (not (empty? formal-params)))
           (block
            (define var (first formal-params))
            (define arg (first args))
            (define (replace-var-to-arg expr)
              (replace expr var arg))

            (invoke (cons 'lambda
                          (cons (rest formal-params)
                                (map replace-var-to-arg
                                     body)))
                    (rest args)))]
          [else
           (error "Кашмар! что-то вообще не то с invoke")]))

  (define (evaluate expr)
    (cond [(lambda-fun? expr)
           expr]
          [(call? expr)
           (block
            (define operator (evaluate  (call-fun expr)))
            (define args     (call-args expr))
            (match operator
              ['begin
               (if (empty? (rest args))
                   (exec (first args))
                   (begin
                     (exec (first args))
                     (exec (cons 'begin
                                 (rest args)))))]
              [lambda-fun?
               (invoke operator
                       args)]
              [_ (error 'bad-operator "Плохой оператор ~A" operator)]))]
          [else
           expr]))
#+end_

* Приложения
** TODO А. Подстановочная, нормальная и аппликативная модели вычисления
** TODO Б. Лексическая область видимости
